home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / archie-1.4.1 / regex.c < prev    next >
C/C++ Source or Header  |  1995-06-18  |  16KB  |  698 lines
  1. #include <pmachine.h>
  2.  
  3. #ifdef NOREGEX
  4. /*
  5.  * These routines are BSD regex(3)/ed(1) compatible regular-expression
  6.  * routines written by Ozan S. Yigit, Computer Science, York University.
  7.  * Parts of the code that are not needed by Prospero have been removed,
  8.  * but most of the accompanying information has been left intact. 
  9.  * This file is to be included on those operating systems that do not
  10.  * support re_comp and re_exec.
  11.  */
  12.  
  13. /*
  14.  * regex - Regular expression pattern matching
  15.  *         and replacement
  16.  *
  17.  * by:  Ozan S. Yigit (oz@nexus.yorku.ca)
  18.  *    Dept. of Computing Services
  19.  *      York University
  20.  *
  21.  * These routines are the PUBLIC DOMAIN equivalents 
  22.  * of regex routines as found in 4.nBSD UN*X, with minor
  23.  * extensions.
  24.  *
  25.  * Modification history:
  26.  *
  27.  * $Log: regex.c,v $
  28.  * Revision 1.1  1991/11/20  02:32:13  brendan
  29.  * entered into RCS
  30.  *
  31.  * Revision 1.1  1991/11/20  02:32:13  brendan
  32.  * entered into RCS
  33.  *
  34.  * Revision 1.3  89/04/01  14:18:09  oz
  35.  * Change all references to a dfa: this is actually an nfa.
  36.  * 
  37.  * Revision 1.2  88/08/28  15:36:04  oz
  38.  * Use a complement bitmap to represent NCL.
  39.  * This removes the need to have seperate 
  40.  * code in the pmatch case block - it is 
  41.  * just CCL code now.
  42.  * 
  43.  * Use the actual CCL code in the CLO
  44.  * section of pmatch. No need for a recursive
  45.  * pmatch call.
  46.  * 
  47.  * Use a bitmap table to set char bits in an
  48.  * 8-bit chunk.
  49.  * 
  50.  * Routines:
  51.  *      re_comp:        compile a regular expression into
  52.  *                      a NFA.
  53.  *
  54.  *            char *re_comp(s)
  55.  *            char *s;
  56.  *
  57.  *      re_exec:        execute the NFA to match a pattern.
  58.  *
  59.  *            int re_exec(s)
  60.  *            char *s;
  61.  *
  62.  * Regular Expressions:
  63.  *
  64.  *      [1]     char    matches itself, unless it is a special
  65.  *                      character (metachar): . \ [ ] * + ^ $
  66.  *
  67.  *      [2]     .       matches any character.
  68.  *
  69.  *      [3]     \       matches the character following it, except
  70.  *            when followed by a left or right round bracket,
  71.  *            a digit 1 to 9 or a left or right angle bracket. 
  72.  *            (see [7], [8] and [9])
  73.  *            It is used as an escape character for all 
  74.  *            other meta-characters, and itself. When used
  75.  *            in a set ([4]), it is treated as an ordinary
  76.  *            character.
  77.  *
  78.  *      [4]     [set]   matches one of the characters in the set.
  79.  *                      If the first character in the set is "^",
  80.  *                      it matches a character NOT in the set, i.e. 
  81.  *            complements the set. A shorthand S-E is 
  82.  *            used to specify a set of characters S upto 
  83.  *            E, inclusive. The special characters "]" and 
  84.  *            "-" have no special meaning if they appear 
  85.  *            as the first chars in the set.
  86.  *                      examples:        match:
  87.  *
  88.  *                              [a-z]    any lowercase alpha
  89.  *
  90.  *                              [^]-]    any char except ] and -
  91.  *
  92.  *                              [^A-Z]   any char except uppercase
  93.  *                                       alpha
  94.  *
  95.  *                              [a-zA-Z] any alpha
  96.  *
  97.  *      [5]     *       any regular expression form [1] to [4], followed by
  98.  *                      closure char (*) matches zero or more matches of
  99.  *                      that form.
  100.  *
  101.  *      [6]     +       same as [5], except it matches one or more.
  102.  *
  103.  *      [7]             a regular expression in the form [1] to [10], enclosed
  104.  *                      as \(form\) matches what form matches. The enclosure
  105.  *                      creates a set of tags, used for [8] and for
  106.  *                      pattern substution. The tagged forms are numbered
  107.  *            starting from 1.
  108.  *
  109.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  110.  *                      previously tagged regular expression ([7]) matched.
  111.  *
  112.  *    [9]    \<    a regular expression starting with a \< construct
  113.  *        \>    and/or ending with a \> construct, restricts the
  114.  *            pattern matching to the beginning of a word, and/or
  115.  *            the end of a word. A word is defined to be a character
  116.  *            string beginning and/or ending with the characters
  117.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  118.  *            followed by any character outside those mentioned.
  119.  *
  120.  *      [10]            a composite regular expression xy where x and y
  121.  *                      are in the form [1] to [10] matches the longest
  122.  *                      match of x followed by a match for y.
  123.  *
  124.  *      [11]    ^    a regular expression starting with a ^ character
  125.  *        $    and/or ending with a $ character, restricts the
  126.  *                      pattern matching to the beginning of the line,
  127.  *                      or the end of line. [anchors] Elsewhere in the
  128.  *            pattern, ^ and $ are treated as ordinary characters.
  129.  *
  130.  *
  131.  * Acknowledgements:
  132.  *
  133.  *    HCR's Hugh Redelmeier has been most helpful in various
  134.  *    stages of development. He convinced me to include BOW
  135.  *    and EOW constructs, originally invented by Rob Pike at
  136.  *    the University of Toronto.
  137.  *
  138.  * References:
  139.  *              Software tools            Kernighan & Plauger
  140.  *              Software tools in Pascal        Kernighan & Plauger
  141.  *              Grep [rsx-11 C dist]            David Conroy
  142.  *        ed - text editor        Un*x Programmer's Manual
  143.  *        Advanced editing on Un*x    B. W. Kernighan
  144.  *        regexp routines            Henry Spencer
  145.  *
  146.  * Notes:
  147.  *
  148.  *    This implementation uses a bit-set representation for character
  149.  *    classes for speed and compactness. Each character is represented 
  150.  *    by one bit in a 128-bit block. Thus, CCL always takes a 
  151.  *    constant 16 bytes in the internal nfa, and re_exec does a single
  152.  *    bit comparison to locate the character in the set.
  153.  *
  154.  * Examples:
  155.  *
  156.  *    pattern:    foo*.*
  157.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  158.  *    matches:    fo foo fooo foobar fobar foxx ...
  159.  *
  160.  *    pattern:    fo[ob]a[rz]    
  161.  *    compile:    CHR f CHR o CCL bitset CHR a CCL bitset END
  162.  *    matches:    fobar fooar fobaz fooaz
  163.  *
  164.  *    pattern:    foo\\+
  165.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  166.  *    matches:    foo\ foo\\ foo\\\  ...
  167.  *
  168.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  169.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  170.  *    matches:    foo1foo foo2foo foo3foo
  171.  *
  172.  *    pattern:    \(fo.*\)-\1
  173.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  174.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  175.  * 
  176.  */
  177.  
  178. #define MAXNFA  1024
  179. #define MAXTAG  10
  180.  
  181. #define OKP     1
  182. #define NOP     0
  183.  
  184. #define CHR     1
  185. #define ANY     2
  186. #define CCL     3
  187. #define BOL     4
  188. #define EOL     5
  189. #define BOT     6
  190. #define EOT     7
  191. #define BOW    8
  192. #define EOW    9
  193. #define REF     10
  194. #define CLO     11
  195.  
  196. #define END     0
  197.  
  198. /*
  199.  * The following defines are not meant
  200.  * to be changeable. They are for readability
  201.  * only.
  202.  *
  203.  */
  204. #define MAXCHR    128
  205. #define CHRBIT    8
  206. #define BITBLK    MAXCHR/CHRBIT
  207. #define BLKIND    0170
  208. #define BITIND    07
  209.  
  210. #define ASCIIB    0177
  211.  
  212. typedef /*unsigned*/ char CHAR;
  213.  
  214. static int  tagstk[MAXTAG];             /* subpat tag stack..*/
  215. static CHAR nfa[MAXNFA];        /* automaton..       */
  216. static int  sta = NOP;                   /* status of lastpat */
  217.  
  218. static CHAR bittab[BITBLK];        /* bit table for CCL */
  219.                     /* pre-set bits...   */
  220. static CHAR bitarr[] = {1,2,4,8,16,32,64,128};
  221.  
  222. static int internal_error;
  223.  
  224. static void
  225. chset(c)
  226. register CHAR c;
  227. {
  228.     bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
  229. }
  230.  
  231. #define badpat(x)    return (*nfa = END, x)
  232. #define store(x)    *mp++ = x
  233.  
  234. char *     
  235. re_comp(pat)
  236. char *pat;
  237. {
  238.     register char *p;               /* pattern pointer   */
  239.     register CHAR *mp = nfa;        /* nfa pointer       */
  240.     register CHAR *lp;              /* saved pointer..   */
  241.     register CHAR *sp = nfa;        /* another one..     */
  242.  
  243.     register int tagi = 0;          /* tag stack index   */
  244.     register int tagc = 1;          /* actual tag count  */
  245.  
  246.     register int n;
  247.     register CHAR mask;        /* xor mask -CCL/NCL */
  248.     int c1, c2;
  249.         
  250.     if (!pat || !*pat)
  251.         if (sta)
  252.             return 0;
  253.         else
  254.             badpat("No previous regular expression");
  255.     sta = NOP;
  256.  
  257.     for (p = pat; *p; p++) {
  258.         lp = mp;
  259.         switch(*p) {
  260.  
  261.         case '.':               /* match any char..  */
  262.             store(ANY);
  263.             break;
  264.  
  265.         case '^':               /* match beginning.. */
  266.             if (p == pat)
  267.                 store(BOL);
  268.             else {
  269.                 store(CHR);
  270.                 store(*p);
  271.             }
  272.             break;
  273.  
  274.         case '$':               /* match endofline.. */
  275.             if (!*(p+1))
  276.                 store(EOL);
  277.             else {
  278.                 store(CHR);
  279.                 store(*p);
  280.             }
  281.             break;
  282.  
  283.         case '[':               /* match char class..*/
  284.             store(CCL);
  285.  
  286.             if (*++p == '^') {
  287.                 mask = 0377;    
  288.                 p++;
  289.             }
  290.             else
  291.                 mask = 0;
  292.  
  293.             if (*p == '-')        /* real dash */
  294.                 chset(*p++);
  295.             if (*p == ']')        /* real brac */
  296.                 chset(*p++);
  297.             while (*p && *p != ']') {
  298.                 if (*p == '-' && *(p+1) && *(p+1) != ']') {
  299.                     p++;
  300.                     c1 = *(p-2) + 1;
  301.                     c2 = *p++;
  302.                     while (c1 <= c2)
  303.                         chset(c1++);
  304.                 }
  305. #ifdef EXTEND
  306.                 else if (*p == '\\' && *(p+1)) {
  307.                     p++;
  308.                     chset(*p++);
  309.                 }
  310. #endif
  311.                 else
  312.                     chset(*p++);
  313.             }
  314.             if (!*p)
  315.                 badpat("Missing ]");
  316.  
  317.             for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  318.                 store(mask ^ bittab[n]);
  319.     
  320.             break;
  321.  
  322.         case '*':               /* match 0 or more.. */
  323.         case '+':               /* match 1 or more.. */
  324.             if (p == pat)
  325.                 badpat("Empty closure");
  326.             lp = sp;        /* previous opcode */
  327.             if (*lp == CLO)        /* equivalence..   */
  328.                 break;
  329.             switch(*lp) {
  330.  
  331.             case BOL:
  332.             case BOT:
  333.             case EOT:
  334.             case BOW:
  335.             case EOW:
  336.             case REF:
  337.                 badpat("Illegal closure");
  338.             default:
  339.                 break;
  340.             }
  341.  
  342.             if (*p == '+')
  343.                 for (sp = mp; lp < sp; lp++)
  344.                     store(*lp);
  345.  
  346.             store(END);
  347.             store(END);
  348.             sp = mp;
  349.             while (--mp > lp)
  350.                 *mp = mp[-1];
  351.             store(CLO);
  352.             mp = sp;
  353.             break;
  354.  
  355.         case '\\':              /* tags, backrefs .. */
  356.             switch(*++p) {
  357.  
  358.             case '(':
  359.                 if (tagc < MAXTAG) {
  360.                     tagstk[++tagi] = tagc;
  361.                     store(BOT);
  362.                     store(tagc++);
  363.                 }
  364.                 else
  365.                     badpat("Too many \\(\\) pairs");
  366.                 break;
  367.             case ')':
  368.                 if (*sp == BOT)
  369.                     badpat("Null pattern inside \\(\\)");
  370.                 if (tagi > 0) {
  371.                     store(EOT);
  372.                     store(tagstk[tagi--]);
  373.                 }
  374.                 else
  375.                     badpat("Unmatched \\)");
  376.                 break;
  377.             case '<':
  378.                 store(BOW);
  379.                 break;
  380.             case '>':
  381.                 if (*sp == BOW)
  382.                     badpat("Null pattern inside \\<\\>");
  383.                 store(EOW);
  384.                 break;
  385.             case '1':
  386.             case '2':
  387.             case '3':
  388.             case '4':
  389.             case '5':
  390.             case '6':
  391.             case '7':
  392.             case '8':
  393.             case '9':
  394.                 n = *p-'0';
  395.                 if (tagi > 0 && tagstk[tagi] == n)
  396.                     badpat("Cyclical reference");
  397.                 if (tagc > n) {
  398.                     store(REF);
  399.                     store(n);
  400.                 }
  401.                 else
  402.                     badpat("Undetermined reference");
  403.                 break;
  404. #ifdef EXTEND
  405.             case 'b':
  406.                 store(CHR);
  407.                 store('\b');
  408.                 break;
  409.             case 'n':
  410.                 store(CHR);
  411.                 store('\n');
  412.                 break;
  413.             case 'f':
  414.                 store(CHR);
  415.                 store('\f');
  416.                 break;
  417.             case 'r':
  418.                 store(CHR);
  419.                 store('\r');
  420.                 break;
  421.             case 't':
  422.                 store(CHR);
  423.                 store('\t');
  424.                 break;
  425. #endif
  426.             default:
  427.                 store(CHR);
  428.                 store(*p);
  429.             }
  430.             break;
  431.  
  432.         default :               /* an ordinary char  */
  433.             store(CHR);
  434.             store(*p);
  435.             break;
  436.         }
  437.         sp = lp;
  438.     }
  439.     if (tagi > 0)
  440.         badpat("Unmatched \\(");
  441.     store(END);
  442.     sta = OKP;
  443.     return 0;
  444. }
  445.  
  446.  
  447. static char *bol;
  448. static char *bopat[MAXTAG];
  449. static char *eopat[MAXTAG];
  450. char *pmatch();
  451.  
  452. /*
  453.  * re_exec:
  454.  *     execute nfa to find a match.
  455.  *
  456.  *    special cases: (nfa[0])    
  457.  *        BOL
  458.  *            Match only once, starting from the
  459.  *            beginning.
  460.  *        CHR
  461.  *            First locate the character without
  462.  *            calling pmatch, and if found, call
  463.  *            pmatch for the remaining string.
  464.  *        END
  465.  *            re_comp failed, poor luser did not
  466.  *            check for it. Fail fast.
  467.  *
  468.  *    If a match is found, bopat[0] and eopat[0] are set
  469.  *    to the beginning and the end of the matched fragment,
  470.  *    respectively.
  471.  *
  472.  */
  473.  
  474. int
  475. re_exec(lp)
  476. register char *lp;
  477. {
  478.     register char c;
  479.     register char *ep = 0;
  480.     register CHAR *ap = nfa;
  481.  
  482.     bol = lp;
  483.  
  484.     bopat[0] = 0;
  485.     bopat[1] = 0;
  486.     bopat[2] = 0;
  487.     bopat[3] = 0;
  488.     bopat[4] = 0;
  489.     bopat[5] = 0;
  490.     bopat[6] = 0;
  491.     bopat[7] = 0;
  492.     bopat[8] = 0;
  493.     bopat[9] = 0;
  494.  
  495.     switch(*ap) {
  496.  
  497.     case BOL:            /* anchored: match from BOL only */
  498.         ep = pmatch(lp,ap);
  499.         break;
  500.     case CHR:            /* ordinary char: locate it fast */
  501.         c = *(ap+1);
  502.         while (*lp && *lp != c)
  503.             lp++;
  504.         if (!*lp)        /* if EOS, fail, else fall thru. */
  505.             return 0;
  506.     default:            /* regular matching all the way. */
  507.         while (*lp) {
  508.             if ((ep = pmatch(lp,ap)))
  509.                 break;
  510.             lp++;
  511.         }
  512.         break;
  513.     case END:            /* munged automaton. fail always */
  514.         return 0;
  515.     }
  516.     if (!ep)
  517.         return 0;
  518.  
  519.     if (internal_error)
  520.         return -1;
  521.  
  522.     bopat[0] = lp;
  523.     eopat[0] = ep;
  524.     return 1;
  525. }
  526.  
  527. /* 
  528.  * pmatch: 
  529.  *    internal routine for the hard part
  530.  *
  531.  *     This code is mostly snarfed from an early
  532.  *     grep written by David Conroy. The backref and
  533.  *     tag stuff, and various other mods are by oZ.
  534.  *
  535.  *    special cases: (nfa[n], nfa[n+1])
  536.  *        CLO ANY
  537.  *            We KNOW ".*" will match ANYTHING
  538.  *            upto the end of line. Thus, go to
  539.  *            the end of line straight, without
  540.  *            calling pmatch recursively. As in
  541.  *            the other closure cases, the remaining
  542.  *            pattern must be matched by moving
  543.  *            backwards on the string recursively,
  544.  *            to find a match for xy (x is ".*" and 
  545.  *            y is the remaining pattern) where
  546.  *            the match satisfies the LONGEST match
  547.  *            for x followed by a match for y.
  548.  *        CLO CHR
  549.  *            We can again scan the string forward
  550.  *            for the single char without recursion, 
  551.  *            and at the point of failure, we execute 
  552.  *            the remaining nfa recursively, as
  553.  *            described above.
  554.  *
  555.  *    At the end of a successful match, bopat[n] and eopat[n]
  556.  *    are set to the beginning and end of subpatterns matched
  557.  *    by tagged expressions (n = 1 to 9).    
  558.  *
  559.  */
  560.  
  561. /*
  562.  * character classification table for word boundary
  563.  * operators BOW and EOW. the reason for not using 
  564.  * ctype macros is that we can let the user add into 
  565.  * our own table. see re_modw. This table is not in
  566.  * the bitset form, since we may wish to extend it
  567.  * in the future for other character classifications. 
  568.  *
  569.  *    TRUE for 0-9 A-Z a-z _
  570.  */
  571. static char chrtyp[MAXCHR] = {
  572.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  573.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  574.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  575.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  576.     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
  577.     1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 
  578.     0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 
  579.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  580.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  581.     1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 
  582.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  583.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  584.     1, 1, 1, 0, 0, 0, 0, 0
  585.     };
  586.  
  587. #define inascii(x)    (0177&(x))
  588. #define iswordc(x)     chrtyp[inascii(x)]
  589. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
  590.  
  591. /*
  592.  * skip values for CLO XXX to skip past the closure
  593.  *
  594.  */
  595.  
  596. #define ANYSKIP    2     /* [CLO] ANY END ...         */
  597. #define CHRSKIP    3    /* [CLO] CHR chr END ...     */
  598. #define CCLSKIP 18    /* [CLO] CCL 16bytes END ... */
  599.  
  600. static char *
  601. pmatch(lp, ap)
  602. register char *lp;
  603. register CHAR *ap;
  604. {
  605.     register int op, c, n;
  606.     register char *e;        /* extra pointer for CLO */
  607.     register char *bp;        /* beginning of subpat.. */
  608.     register char *ep;        /* ending of subpat..     */
  609.     char *are;            /* to save the line ptr. */
  610.  
  611.     while ((op = *ap++) != END)
  612.         switch(op) {
  613.  
  614.         case CHR:
  615.             if (*lp++ != *ap++)
  616.                 return 0;
  617.             break;
  618.         case ANY:
  619.             if (!*lp++)
  620.                 return 0;
  621.             break;
  622.         case CCL:
  623.             c = *lp++;
  624.             if (!isinset(ap,c))
  625.                 return 0;
  626.             ap += BITBLK;
  627.             break;
  628.         case BOL:
  629.             if (lp != bol)
  630.                 return 0;
  631.             break;
  632.         case EOL:
  633.             if (*lp)
  634.                 return 0;
  635.             break;
  636.         case BOT:
  637.             bopat[*ap++] = lp;
  638.             break;
  639.         case EOT:
  640.             eopat[*ap++] = lp;
  641.             break;
  642.          case BOW:
  643.             if (lp!=bol && iswordc(lp[-1]) || !iswordc(*lp))
  644.                 return 0;
  645.             break;
  646.         case EOW:
  647.             if (lp==bol || !iswordc(lp[-1]) || iswordc(*lp))
  648.                 return 0;
  649.             break;
  650.         case REF:
  651.             n = *ap++;
  652.             bp = bopat[n];
  653.             ep = eopat[n];
  654.             while (bp < ep)
  655.                 if (*bp++ != *lp++)
  656.                     return 0;
  657.             break;
  658.         case CLO:
  659.             are = lp;
  660.             switch(*ap) {
  661.  
  662.             case ANY:
  663.                 while (*lp)
  664.                     lp++;
  665.                 n = ANYSKIP;
  666.                 break;
  667.             case CHR:
  668.                 c = *(ap+1);
  669.                 while (*lp && c == *lp)
  670.                     lp++;
  671.                 n = CHRSKIP;
  672.                 break;
  673.             case CCL:
  674.                 while ((c = *lp) && isinset(ap+1,c))
  675.                     lp++;
  676.                 n = CCLSKIP;
  677.                 break;
  678.             default:
  679.                 internal_error++;
  680.                 return 0;
  681.             }
  682.  
  683.             ap += n;
  684.  
  685.             while (lp >= are) {
  686.                 if (e = pmatch(lp, ap))
  687.                     return e;
  688.                 --lp;
  689.             }
  690.             return 0;
  691.         default:
  692.             internal_error++;
  693.             return 0;
  694.         }
  695.     return lp;
  696. }
  697. #endif /* Need regex libraries? Compile to nothing if not.  */
  698.